#include "bm.h"
int bm_search1(const string& target,const string& pattern){
	int target_len = target.size();
	int pattern_len = pattern.size();
	int target_idx = pattern_len;
	int pattern_idx ;

	if (pattern_len == 0) 
		return -1;

	while(target_idx <= target_len){
		pattern_idx = pattern_len;
		 while(target[--target_idx] == pattern[--pattern_idx])
			 if (pattern_idx == 0)
				 return target_idx;
	 	 target_idx += (pattern_len - pattern_idx) + 1;
	} 
}

void good_suffix_shift(const string& pattern,int* shift){
	size_t pattern_len = pattern.size();
	shift[pattern_len - 1] = 1; //
	char end_val = pattern[pattern_len - 1];

	string::const_iterator p_prev;
	string::const_iterator p_next;
	string::const_iterator p_temp;
	string::const_iterator p_now = pattern.begin() + pattern_len - 2;
	bool good_suffix = false; //

	for (int i = pattern_len - 2; i >= 0; --i,--p_now){
		good_suffix = false;
		p_temp = pattern.begin() + pattern_len - 2;
		while (true){
			while (p_temp >= pattern.begin()){
				if (*p_temp == end_val){
					--p_temp;
					break;
				}
				else 
					--p_temp;
			}

			p_prev = p_temp;
			p_next = pattern.begin() + pattern_len - 2;
			if (p_prev < pattern.begin() && *(p_temp + 1) != end_val) //not found1
				break;

			bool match_flag = true;
			while (p_prev >= pattern.begin() && p_next > p_now){
				if (*p_prev -- != *p_next--){
					match_flag = false; // match failed
					break;
				}
			}
			if (!match_flag) continue; 
			else {
				if (p_prev < pattern.begin() || * p_prev != *p_next){
					good_suffix = true;
					break;
				}
			}
		}
		shift[i] = pattern_len - i + p_next - p_prev;
		if (good_suffix)
			shift[i]--;
	}
}

void bad_char_shift(const string& pattern,int* shift){
	size_t pattern_len = pattern.size();
	size_t len = pattern_len;
	for (int i = 0; i < 256; ++i)
		shift[i] = pattern_len;

	for (int i = 0; i < pattern_len; ++i){
		shift[static_cast<unsigned int>(pattern[i])] = --len;
	}
	//for (int i = 0; i < pattern_len; ++i)
	//	cout<<shift[static_cast<unsigned int>(pattern[i])]<<"_";
}

int bm(const string& target,const string& pattern){
	int target_len = target.size();
	int pattern_len = pattern.size();
	int * bad_char = new int[256];
	int * good_suffix = new int[pattern_len];
	int pattern_idx;
	int target_idx = pattern_len;
	int good_stride, bad_stride;

	bad_char_shift(pattern,bad_char);
	good_suffix_shift(pattern,good_suffix);

	while (target_idx <= target_len){
		pattern_idx = pattern_len;
		while (target[--target_idx] == pattern[--pattern_idx]){
			if (pattern_idx == 0){
				delete [] bad_char;
				delete [] good_suffix;
				return target_idx;
			}
		}
		good_stride = good_suffix[pattern_idx];
		bad_stride = bad_char[pattern_idx];
		target_idx += ((good_stride > bad_stride) ? good_stride : bad_stride) + 1;
	}
	delete [] bad_char;
	delete [] good_suffix;
	return -1;
}

